package one.one.twentySeven;

import com.sun.org.apache.regexp.internal.RE;

public class Binomial {

	static int count = 0;

	public static double binomial(int N, int k, double p) {

		if (N == 0 && k == 0)
			return 1.0;
		if (N < 0 || k < 0)
			return 0.0;

		return (1 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
	}

	static double bi(int N, int k, double p) {
		double[][] r = new double[N + 1][k + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j <= k; j++) {
				r[i][j] = -1;
			}
		}
		for (int i = 0; i <= N; i++) {
			r[i][0] = Math.pow(1 - p, i);
		}
		r[0][0] = 1.0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= k; j++) {
				r[i][j] = (1.0 - p) * r[i - 1][j] + p * r[i - 1][j - 1];
			}
		}
		return r[N][k];
	}

	public static void main(String[] args) {
		long s=System.currentTimeMillis();
		System.out.println(binomial(50,20, 0.25));
		System.out.println("Dur:"+(System.currentTimeMillis()-s));
		s=System.currentTimeMillis();
		System.out.println(bi(50, 20, 0.25));
		System.out.println("Dur:"+(System.currentTimeMillis()-s));
	}

}
